Recently, technical innovation has yielded higher operating speeds of central processing units (CPUs) of computers. Thus, the time required for memory access is relatively longer than the time taken to read out data from registers of the CPU. To improve processing speed of the entire program, it is increasingly important to hold as many variable values for use in the program as possible in registers so as to reduce the number of memory accesses.
Conventionally, an optimizing compiler has a register assignment function for effectively assigning variables in an object program targeted for optimization to registers in order to reduce the number of memory accesses and improve the efficiency of the overall processing. The optimizing compiler causes the registers to hold variable values assigned to the registers and the memory to store variable values judged as being unassignable to the register. The optimizing compiler generates spill-in instructions to read out the variable values from the memory, prior to instructions to refer to the variable values stored in the memory.
The following documents are considered:                [Non-Patent Document 1] J. Knoop et al., “The Power of Assignment Motion,” PLDI '95        [Non-Patent Document 2] R. Gupta and R. Bodik, “Register Pressure Sensitive Redundancy Elimination,” Proceedings of the 8th International Conference on Compiler Construction, LNCS 1575, pp. 107-121 (1999).        
Meanwhile, a redundancy elimination technique is used in recent optimizing compilers to improve the efficiency of the overall processing by eliminating redundant instructions among the plurality of instructions. In many cases, the optimizing compilers change instruction execution locations in order to effectively eliminate redundancy. To change instruction execution locations, a technique has been conventionally used to perform control so as not to generate additional variables which store the operation results of the instructions. (See Non-Patent Document 1). An alternative technique has been proposed to change instruction execution locations within a range that additional spilling does not take place even when variables are assigned to registers. (See Non-Patent Document 2).
The above-mentioned techniques of redundancy elimination are applicable to the spill-in instructions. However, according to Non-Patent Document 1, there is a problem that the range of a change in spill-in instruction execution locations is limited when target registers, from which data is to be read out by spill-in instructions, are used by other instructions. The technique described in Non-Patent Document 2 cannot determine registers assigned to variables although the technique can detect the range that permits a change in the instruction execution locations for instructions targeted for redundancy elimination.